package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}9:01
 */
public class H1 {//正则表达式匹配

    public static void main(String[] args) {
        String text = "aa";
        String pattern = "a*";
        boolean result = new H1().isMatch(text,pattern);
        System.out.println(result);
    }

    public boolean isMatch(String text, String pattern) {
        if (text==null||pattern==null){
            return false;
        }
        return  matchCore(text.toCharArray(),pattern.toCharArray(),0,0);
    }

    private static boolean matchCore(char[] str,char[] pattern,int i,int j){
        if (j == pattern.length){
            return i == str.length;//模板到头 如果字符串也到头则成功如果没有则失败
        }
        //注意防止数组索引OutOfBounds
        if (j < pattern.length-1 && pattern[j + 1] == '*'){//如果下一个为*则进行1匹配
            if (i<str.length &&(str[i] == pattern[j]||(pattern[j]=='.'))){//在第二位为时*一般情况的匹配
                return matchCore(str,pattern,i+1,j)||matchCore(str,pattern,i,j+2);
            }else {//当前不匹配直接后移两位
                return matchCore(str,pattern,i,j+2);
            }
        }
        if (str.length != i && (str[i]==pattern[j]||pattern[j]=='.')){
            return matchCore(str,pattern,i+1,j+1);
        }
        return false;//如果两者都不是直接失败
    }
}
